#include <iostream>

using namespace std;

void printArray(int array[], int arrLen) {
    for (int i = 0; i < arrLen; ++i) {
        cout << array[i] << " ";
    }
    cout << endl;
}

int binarySearchFirstEqual(int searchKey, int array[], int arrLen) {
   int low = 0;
   int high = arrLen - 1;
   int keyPos = -1;

   while (low <= high) {
        int mid = low +((high - low + 1) >> 1);
        if (array[mid] > searchKey) {
            high = mid - 1;
        }
        else if (array[mid] < searchKey){
            low = mid + 1;
        }
        else {
            if (mid == 0 || array[mid - 1] != searchKey) {
                keyPos = mid;
                break;
            }
            else {
                high = mid - 1;
            }
        }
   }

   return keyPos;
}

int binarySearchLastEqual(int searchKey, int array[], int arrLen) {
   int low = 0;
   int high = arrLen - 1;
   int keyPos = -1;

     while (low <= high) {
        int mid = low +((high - low + 1) >> 1);
        if (array[mid] > searchKey) {
            high = mid - 1;
        }
        else if (array[mid] < searchKey){
            low = mid + 1;
        }
        else {
            if (mid == arrLen - 1 || array[mid + 1] != searchKey) {
                keyPos = mid;
                break;
            }
            else {
                low = mid + 1;
            }
        }
    }

   return keyPos;
}

int binarySearchFirstLargerEqual(int searchKey, int array[], int arrLen) {
   int low = 0;
   int high = arrLen - 1;
   int keyPos = -1;

     while (low <= high) {
        int mid = low +((high - low + 1) >> 1);
        if (array[mid] >= searchKey) {
            if (mid == 0 || array[mid - 1] < searchKey) {
                keyPos = mid;
                break;
            }
            else {
                high = mid - 1;
            }
            
        }
        else {
            low = mid + 1;
        }
    }

   return keyPos;
}

int binarySearchLastSmallerEqual(int searchKey, int array[], int arrLen) {
   int low = 0;
   int high = arrLen - 1;
   int keyPos = -1;

     while (low <= high) {
        int mid = low +((high - low + 1) >> 1);
        if (array[mid] <= searchKey) {
            if (mid == arrLen - 1 || array[mid + 1] > searchKey) {
                keyPos = mid;
                break;
            }
            else {
                low = mid + 1;
            }
            
        }
        else {
            high = mid - 1;
        }
    }

   return keyPos;
}



int main(){
    int array0[] = {1, 1, 2, 3, 4, 5, 6};
    int arrayLen = sizeof(array0)/sizeof(int);

    printArray(array0, arrayLen);
    cout << "First Array Pos of 1: "<< binarySearchFirstEqual(1, array0, arrayLen) << endl;
    cout << "Last Array Pos of 1: "<< binarySearchLastEqual(1, array0, arrayLen) << endl;
    cout << "First Larger Equal Array Pos of 1: "<< binarySearchFirstLargerEqual(1, array0, arrayLen) << endl;
    cout << "Last Smaller Equal Array Pos of 1: "<< binarySearchLastSmallerEqual(1, array0, arrayLen) << endl;

    cout << "=========================================" << endl;

    int array1[] = {1, 2, 2, 3, 3, 5, 6, 8};
    arrayLen = sizeof(array1)/sizeof(int);
   
    printArray(array1, arrayLen);
    cout << "First Array Pos of 3: "<< binarySearchFirstEqual(3, array1, arrayLen) << endl;
    cout << "Last Array Pos of 3: "<< binarySearchLastEqual(3, array1, arrayLen) << endl;
    cout << "First Larger Equal Array Pos of 3: "<< binarySearchFirstLargerEqual(3, array1, arrayLen) << endl;
    cout << "Last Smaller Equal Array Pos of 3: "<< binarySearchLastSmallerEqual(3, array1, arrayLen) << endl;

    cout << "=========================================" << endl;

    int array2[] = {1, 2, 2, 3, 3, 5, 6, 8};
    arrayLen = sizeof(array2)/sizeof(int);

    printArray(array2, arrayLen);
    cout << "First Array Pos of 4: "<< binarySearchFirstEqual(4, array2, arrayLen) << endl;
    cout << "Last Array Pos of 4: "<< binarySearchLastEqual(4, array2, arrayLen) << endl;
    cout << "First Larger Equal Array Pos of 4: "<< binarySearchFirstLargerEqual(4, array2, arrayLen) << endl;
    cout << "Last Smaller Equal Array Pos of 4: "<< binarySearchLastSmallerEqual(4, array2, arrayLen) << endl;

    cout << "=========================================" << endl;
}